package hot100.链表.不需要虚拟头;

import hot100.链表.ListNode;

/** 160 相交链表
/**
 *     a1 → a2
 *             ↘
 *               c1 → c2 → c3
 *             ↗
 *  b1 → b2 → b3
 */
public class crossChain160 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {return null;}

        int aCount = 0; int bCount = 0;
        ListNode temA = headA;
        while (temA != null) {temA = temA.next; aCount++;}
        ListNode temB = headB;
        while (temB != null) {temB = temB.next; bCount++;}

        /**节点是不支持向前的 所以需要操作临时节点**/
        temA = headA; temB = headB;
        if (aCount > bCount) {
            for (int i = 0; i < aCount - bCount; i++) {
                temA = temA.next;
            }
        } else {
            for (int i = 0; i < bCount - aCount; i++) {
                temB = temB.next;
            }
        }

        /**关于到底 .next不会校验最后一个**/
        while (temA != null) {
            if (temA == temB) { return temA;}
            temA = temA.next;
            temB = temB.next;
        }
        return null;
    }

    public ListNode genusMethod(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

    public static void main(String[] args) {
        crossChain160 obj = new crossChain160();
        ListNode template1 = getTemplate1();
        ListNode value = obj.genusMethod(template1, getTemplate2(template1));
        System.out.println(value.val);
    }

    public static ListNode getTemplate1() {
        ListNode temp = new ListNode(1);
        temp.next = new ListNode(9);
        temp.next.next = new ListNode(1);
        temp.next.next.next = new ListNode(2);
        temp.next.next.next.next = new ListNode(4);
        return temp; //[1,9,1,2,4]
    }

    public static ListNode getTemplate2(ListNode headA) {
        ListNode temp = new ListNode(3);
        temp.next = headA.next.next.next; //[3] 然后接到 [1,9,1,2,4] index为3
        return temp;
    }
}